#include <bits/stdc++.h>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
};
class Solution
{
  public:
    ListNode *oddEvenList(ListNode *head)
    {
        // write code here
        if (head == nullptr)
        {
            return nullptr;
        }
        vector<ListNode *> arr;
        ListNode *cur = head;
        while (cur != nullptr)
        {
            arr.emplace_back(cur);
            cur = cur->next;
        }
        // 放奇数
        ListNode *newHead = arr[0];
        ListNode *Newcur = newHead; // 重新回到头准备遍历
        for (int i = 0; i < arr.size(); i += 2)
        {
            Newcur->next = arr[i];
            Newcur = Newcur->next;
        
        // 放偶数
        for (int i = 1; i < arr.size(); i += 2)
        {
            Newcur->next = arr[i];
            Newcur = Newcur->next;
        }
        Newcur->next = nullptr;
        return newHead;
    }
};